1. Field of the Invention
The present invention relates generally to a routing technique for forwarding packets to a destination in the Internet, and in particular, to an apparatus and method for performing a high-speed IP (Internet Protocol) route lookup and managing a routing (or forwarding) table.
2. Description of the Related Art
According to the increasing number of Internet users, variety of supported services and the expansion of service areas such as VoIP (Voice over Internet Protocol) and stream-oriented applications, the traffic in the Internet has been increased exponentially. Forwarding packets to the next hop interface by finding a destination path without causing any delay in a Giga or Tera bps-class high-speed router has emerged as a contingent design issue. In order to find the destination path of the packets forwarded over physical input interfaces of the router, maintaining a routing (or forwarding) table in a compact form and reducing lookup time are required.
In a conventional router, before the advent of recently deployed high-speed routers where a required time to process packets and find their destinations is faster than the one on the transmission paths, a router, as a relaying node connecting subnetworks or other networks, has played its roles well. Recently, the bandwidth increase of optical networking interface such as POS OC-192 (10 Gbps) or IP over DWDM (Dense Wavelength Division Multiplexing) has surpassed a processing time in a router and raised blame that a router causes a dominant bottleneck in a high-speed Internet. For a background discussion on Routers see: Keshav, S. and Sharma, R., Issues and Trends in Router Design, IEEE Communications Magazine, pages 144–151,May,1998; Kumar, V. and Lakshman, T. and Stiliadis, D., Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet, IEEE Communications Magazine, pages 152–164, May,1998; Chan, H., Alnuweiri, H. and Leung, V., A Framework for Optimizing the Cost and Performance of Next-Generation IP Routers, IEEE Journal of Selected Areas in Communications, Vol. 17, No.6, pages 1013–1029, June 1999; Partridge, C. et al., A 50-Gb/s IP Router, IEEE/ACM Trans. on Networking, vol. 6, no.3, pages 237–248, 1998; and Metz, C., IP Routers: New Tool for Gigabit Networking, IEEE Internet Computing, pages 14–18, November–December, 1998.
In the early 1990s, a working group of an IETF (Internet Engineering Task Force) introduced a new IP addressing scheme called CIDR (Classless Inter-Domain Routing) to use IP addresses efficiently in IPv4 (IP version 4). See RFC (Request for Comments: Network Working Group) 1518, An Architecture for IP Address Allocation with CIDR, September 1993; and RFC 1517, Applicability Statement for the Implementation of Classless Inter-Domain Routing (CIDR), September 1993.
In this case, in order to grasp a prefix in the packets having various prefix lengths and find an IP address matching to the longest prefix, an LPM (Longest Prefix Matching) algorithm based on a trie or Patricia (Practical Algorithm to Retrieve Information Coded as Alphanumeric) trie data structure has been widely used. See Doeringer, W., Kaijoth, G. and Nassehi, M., Routing on Longest-Matching Prefixes, IEEE/ACM Trans. on Networking, vol.4, no. 1, pages 86–97, February, 1996.
The LPM algorithm will be described in detail with reference to Table 1 below. Table 1 shows a simple example of routing entries contained in a routing (or forwarding) table. The asterisk allows the padding of any number with ‘0’ or ‘1’ although the prefix per se cannot exceed 32 in the case of IPv4. For example, ‘0*’ implies ‘01*’, ‘011*’ or ‘010*’, no matter what the rest of bit strings are.
TABLE 1PrefixInterface0*0001010*10010101*100101011*111*1111*0110*111110*01100101011*11100101010*111001010101*10
The routing entry or route is represented by IP-address:: ={<network prefix>,<host number>}. When a destination IP address is ‘10010101000 . . . 0’, the first bit of the destination IP address is compared with the network prefixes (simply prefixes) contained in the routing table. Thus, prefixes such as ‘0*’, ‘01010*’, ‘010101*’ and ‘0101011*’ are discarded because these ones have the first bit starting from ‘0’. When the given destination address is compared with the rest of prefixes, prefixes ‘11*’, ‘1110*’ and ‘1001010101*’ are excluded because they are not matching with the destination address from the second or 10th bit. Among the plausible prefixes (e.g., ‘1*’, ‘10*’ and ‘100101010*’), ‘100101010*’ is chosen as the longest prefix (or most specific) matching route and the IP packet with the destination IP address is forwarded to the adjacent router through the interface ‘10’.
Meanwhile, a recently announced routing lookup algorithm is stored in a cache memory in a possible processor (routing processor or forwarding engine) to reduce a memory access time. Although the routing lookup algorithm based on the routing table secures an efficient lookup, it cannot change the routing (or forwarding) table. Hence, the routing lookup algorithm may cause time delay in reflecting the routing table, when changed.
In addition, a routing table in a routing processor is copied through a DMA (Direct Memory Access) card, an IPC (Inter-Processor Communication) card or a switch fabric, and then applied to a forwarding table in the forwarding engine. At this point, it is necessary to build up a new forwarding table rather than adding and deleting only the changed routes. This may cause additional time delay, and also cause a bottleneck in an internal memory of the router or a system bus due to an increase in the memory bandwidth in use at a memory access request from the router.
Furthermore, in the case of some algorithms, an initial routing (or forwarding) table must be built up using link reachability information representing the current link state of the router. Therefore, in order to sequentially insert the link reachability information in the routing table, an additional process to sort every route according to prefix lengths in advance is required. See Degermark, M., Brodnik, A., Carlsson, S. and Pink, S., Small Forwarding Tables for Fast Routing Lookups, In Proceedings of ACM SJGCOMM '97, pages 3–14, Cannes, France, 1997; Srinivasan, V. and Varghese, G., Faster IP Lookups using Controlled Prefix Expansion, In Proceedings of ACM Sigmetrics '98 Conf., pages 1–11, 1998; Lampson, B., Srinivasan, V. and Varghese, G., IP Lookups using Multiway and Multicolumn Search, In IEEE Infocom, pages 1248–1256,1998; Tzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1067–1082, June, 1999; Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable High Speed IP Routing Lookups, In Proceedings of ACM SIGCOMM '97, Cannes, France, pages 25–37, 1997; and Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable Best Matching Prefix Lookups, In Proceedings of PODC '98, Puerto Vallarta, page, 1998.
Typically used data structures in a routing table such as a radix tree or a Patricia trie not only cause an increase in number of memory accesses required to find a packet path, but also require a considerable update time to reflect the changed routes caused by setting or deleting routes from the neighboring routers of the corresponding router. Degermark, M., Brodnik, A., Carlsson, S. and Pink, S., Small Forwarding Tables for Fast Routing Lookups, in Proceedings of ACM SIGCOMM '97, pages 3–14, Cannes, France, 1997, proposed a compact forwarding table which can be stored in a cache of the forwarding engine, but it is hard to reflect the changed routes into it. A controlled prefix expansion method proposed by Srinivasan, V. and Varghese, G., Faster IP Lookups using Controlled Prefix Expansion, In Proceedings of ACM Sigmetrics '98 Conf., pages 1–11, 1998 (see U.S. Pat. No. 6,011,795, issued to George Varghese and Srinivasan and entitled Method and Apparatus for Fast Hierarchical Address Lookup Using Controlled Expansion of Prefixes) and a fast address-lookup algorithm proposed by Tzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1067–1082, June, 1999 are also based on a multi-resolution trie, but it is hard to add and delete the routes because the data structures are based on the trie. In this connection, refer to U.S. Pat. No.6,061,712 entitled Method for IP Routing Table Look-up and U.S. Pat. No. 6,067,574, entitled High Speed Routing Using Compressed Tree Process, both issued to Hong-Yi Tzeng. A rope search algorithm (Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable High Speed IP Routing Lookups, In Proceedings of ACM SIGCOMM '97, Cannes, France, pages 25–37, 1997; and Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable Best Matching Prefix Lookups, In Proceedings of PODC '98, Puerto Vallarta, page, 1998) by mapping a trie structure to a binary tree with hash tables and a complete prefix trie based on multi-resolution trie by (Tzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1067–1082, June, 1999) tend to be inefficient due to the update of the changed route entries because those data structures are based on the trie. In this connection, refer to U.S. Pat. No. 6,018,524 issued to Jonathan Turner, George Varghese and Marcel Waldvogel and entitled Scalable High Speed IP Routing Lookups. 
Aside from the above, other variants of the trie have been proposed. For example, a two-trie scheme (Kijkanjanarat, T. and Chao, H., Fast IP Lookups Using a Two-trie Data Structure, In Proceedings of Globecom '99, 1999) by linking two tries to reduce the search time and an LC-trie (Nillson, S. and Karlsoson, G., IP-Addresses Lookup Using LC-Tries, IEEE Journal on Selected Areas in Communications, Vol.17, No. 16, pages 1083–1092, 1999) to reduce level length in a trie, and a DP-trie (Doeringer, W., Kaijoth, G. and Nassehi, M., Routing on Longest-Matching Prefixes, IEEE/ACM Trans. on Networking, vol.4, no.1, pages 86–97, February, 1996) have been suggested. They still have difficulties, however, in reflecting the changed routes into the routing (or forwarding) table.
In addition, although previously mentioned schemes contribute to a reduction in lookup time, there still exists a problem concerning route updates. Hardware-assisted schemes are also suggested to reduce the lookup time. Gupta, P., Lin, S. and McKeown, N., Routing Lookups in Hardware at Memory Access Speeds, In Proceedings of IEEE INFOCOM '98 Conf., pages 1240–1247, 1998, proposed a solution based on the use of large-scale memory. Reducing the lookup time is possible in comparisons with software-based ones, but it still poses significant amount of memory use and cost in the transition of IPv6. A scheme using CAM (Content Addressable Memory) was suggested by McAuley, A. and Francis, P., Fast Routing Table Lookup Using CAMs, In Proceedings of IEEE INFOCOM '93, Vol.3, pages 1382–1391, 1993, but due to the high price of CAM, it is not being I a: considered for use at present. Huang, N. and Zhao, S., A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pages 1093–1104, June, 1999, proposes an indirect lookup algorithm using a pipelined memory access to reduce memory accesses although it has a disadvantage over IPv6 transition.